#include <iostream>
#include <vector>

using namespace std;
void bubble_sort1 (vector<int>& v) {
	int len = v.size();
	int i,j;
	for(i = 0; i < len - 1; i++) {//len轮，每轮确定一个元素的位置
		for(j = 0;j < len - 1 - i; j++) {
			if(v[j] > v[j + 1])
				swap(v[j],v[j + 1]);
		}
	}
}

void bubble_sort2 (vector<int>& v) {
	int len = v.size();
	int i,j;
	bool exchanged;
	for(i = 0; i < len - 1; i++) {
		exchanged = false;
		for(j = 0; j < len - 1 - i; j++) {
			if(v[j] > v[j+1])
			{
				exchanged = true;
				swap(v[j], v[j+1]);
			}
		}
		if(!exchanged)//如果一轮没有发生交换，则说明序列此时已经有序
			break;
	}
}

//最好情况下能达到O(N)的时间复杂度，但本质上没有质的提升
void bubble_sort3 (vector<int>& v) {
	bool exchanged = true;
	int last_exchanged_index = -1;
	int index_of_lastunsorted_element = v.size() - 1;
	int i;
	while(exchanged) {
		exchanged = false;
		for(i = 0; i < index_of_lastunsorted_element; i++) {
			if(v[i] > v[i + 1]) {
				swap(v[i], v[i + 1]);
				last_exchanged_index = i;
				exchanged = true;
			}
		}
		index_of_lastunsorted_element = last_exchanged_index;
	}
}

int main() {
	vector<int> v{1,4,3,2,7,9,5,10,6,3};
	for(auto& t : v)
		cout << t << " ";
	cout << endl;
	//bubble_sort1(v);
	//bubble_sort2(v);
	bubble_sort3(v);
	for(auto& t : v)
		cout << t << " ";
	cout << endl;
	return 0;
}

/*
原地交换两个数字：
//先加后减
arr[j + 1] = arr[j + 1] + arr[j];
arr[j] = arr[j + 1] - arr[j];
arr[j + 1] = arr[j + 1] - arr[j];

//先减后加
arr[j + 1] = arr[j] - arr[j + 1];
arr[j] = arr[j] - arr[j + 1];
arr[j + 1] = arr[j + 1] + arr[j];

//位运算
arr[i] = arr[i] ^ arr[j];
arr[j] = arr[j] ^ arr[i];
arr[i] = arr[i] ^ arr[j];
*/
//平均时间复杂度为O(N^2),空间复杂度为O(1);